(a) Technical Field
Embodiments of the present disclosure are directed an error correcting code (ECC) with its accompanied class of decoding algorithms, and more particularly, on a variation of a channel polarization code.
(b) Discussion of the Related Art
Block codes are an important family of ECCs. These codes operate on fixed blocks of information bits. In each encoding operation a vector of k information bits is encoded to a (redundant) vector of N symbols, which in the case of binary codes is N bits. The number of coded bits N is called the block length of the code.
A polar code is a linear block error correcting code developed by Erdal Arikan that is the first code with an explicit construction that achieves the channel capacity for symmetric binary-input, discrete, memoryless channels (B-DMC) under practical complexity. Polar codes are defined as codes of length N=2n, n a positive integer, and there exits algorithms for which the decoding complexity is O(N log N). For example, for n=10 there is a length 1024 polar code.
Polar codes may be appropriate codes for NAND flash devices, due to their capacity achieving properties. One of the first issues that have to be solved to design polar ECC schemes for NAND flash devices is length compatibility. In various applications of ECC in general, the length of the codes needs to be adjusted to fit a given length. However, in many families of codes, as in the case of channel polarization codes, the block length cannot be chosen arbitrarily and there are many off-the-shelf methods known in the literature to tackle this situation. In many communication and storage systems, such as solid state drives and other NAND Flash memory devices, the number of information bits k is an integral power of two, which makes the block length not an integral power of two. Known method of shortening and puncturing may be applied also for this code, as suggested by various authors in past years. The decoding complexity of an ECC scheme is another important performance characteristic of an ECC system. Off-the-shelf methods for adjusting the block length of a code end up with a decoding complexity that relates to the original block length of the codes, before the adjustments. In many cases, as in the channel polarization codes, the original block length is larger (sometimes, much larger, e.g. approximately doubles) than the target block lengths. This can cause the decoding complexity to be substantially larger than that expected due to the actual transmitted/stored block.
For example, one technique called puncturing involves not transmitting certain bits, and operating the FULL decoder for a full length polar code while fixing no usable information (LLR=0) for the punctured bits. The operations are carried on the complete code graph and therefore the complexity matches that of a full length polar code and not a punctured length polar code. An alternative conventional method is called shortening, which involves operating a full decoder with infinite (maximal level) LLR values. This method allows encoding the information bits in such a way that some of the coded bits are known a-priori (e.g. 0 bits). That is why these bits need not be stored or transmitted in a communication scenario. At the decoder however, the FULL decoder is operated while having perfect information for the shortened bits.